package graph.unweighted.dfs.path;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: SingleSourcePath.java 
 * @Package graph.dfs 
 * @Description: 应用DFS求解任意两点之间的路径
 * @author CandyWall   
 * @date 2021年1月15日 上午11:37:25 
 * @version V1.0
 */
public class CandyPath {
    private CandyGraph graph;        // 图
    private int s;  // 起点
    private int t;  // 终点
    private int[] pres;    // 记录深度优先遍历过程中某一个顶点的前一个顶点
    
    private boolean[] visited;  // 记录顶点是否被遍历过，默认都为false
    /**
     * 
     * @param graph ：图
     * @param s     ：图中一个顶点，作为单源路径的源
     */
    public CandyPath(CandyGraph graph, int s, int t) {
        this.graph = graph;
        graph.validateVertex(s);
        graph.validateVertex(t);
        this.s = s;
        this.t = t;
        pres = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            pres[i] = -1;
        }
        visited = new boolean[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = false;
        }
        dfs(s, s);
        
        System.out.println(Arrays.toString(visited));
    }
    
    /**
     * 深度优先遍历
     */
    private boolean dfs(int v, int pre) {
        visited[v] = true;
        pres[v] = pre;
        if(v == t)
            return true;
        for(int w : graph.adjacentVertexes(v)) {
            if(!visited[w]) {
                if(dfs(w, v))  // 顶点w是从v这个顶点来的
                    return true;
            }
        }
        return false;
    }
    
    /**
     * 判断顶点s到顶点t是否可达
     * @return
     */
    public boolean isConnected(int t) {
        return visited[t];
    }
    
    /**
     * 获取顶点s到顶点t的单源路径
     * @return
     */
    /*public ArrayList<Integer> getSingleSourcePath() {
        if(!isConnected()) {
            return null;
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        path.add(s);
        getSingleSourcePath(t, path);
        return path;
    }
    
    private void getSingleSourcePath(int v, ArrayList<Integer> list) {
        if(pres[v] == v) {
            return;
        }
        getSingleSourcePath(pres[v], list);
        list.add(v);        
    }*/
    
    /**
     * 获取顶点s到顶点t的单源路径
     * @return
     */
    public ArrayList<Integer> getPath() {
        if(!isConnected(t)) {
            return null;
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        int cur = t;
        while(cur != s) {
            path.add(cur);
            cur = pres[cur];
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }
    
    public int[] getPres() {
        return pres;
    }

    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/graph.txt");
        int s = 0;
        int t = 6;
        CandyPath path = new CandyPath(graph, s, t);
        System.out.println("从顶点 " + s + " 出发到 " + t + " 的路径为：" + path.getPath());
    }
}
